{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Path Visiting All Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #breadth-first-search #graph #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #广度优先搜索 #图 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestPathLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #访问所有节点的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>存在一个由 <code>n</code> 个节点组成的无向连通图，图中的节点按从 <code>0</code> 到 <code>n - 1</code> 编号。</p>\n",
    "\n",
    "<p>给你一个数组 <code>graph</code> 表示这个图。其中，<code>graph[i]</code> 是一个列表，由所有与节点 <code>i</code> 直接相连的节点组成。</p>\n",
    "\n",
    "<p>返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/12/shortest1-graph.jpg\" style=\"width: 222px; height: 183px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,2,3],[0],[0],[0]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>一种可能的路径为 [1,0,2,0,3]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/12/shortest2-graph.jpg\" style=\"width: 382px; height: 222px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>一种可能的路径为 [0,1,4,2,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == graph.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 12</code></li>\n",
    "\t<li><code>0 &lt;= graph[i].length &lt;&nbsp;n</code></li>\n",
    "\t<li><code>graph[i]</code> 不包含 <code>i</code></li>\n",
    "\t<li>如果 <code>graph[a]</code> 包含 <code>b</code> ，那么 <code>graph[b]</code> 也包含 <code>a</code></li>\n",
    "\t<li>输入的图总是连通图</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-path-visiting-all-nodes](https://leetcode.cn/problems/shortest-path-visiting-all-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-path-visiting-all-nodes](https://leetcode.cn/problems/shortest-path-visiting-all-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[0],[0],[0]]', '[[1],[0,2,4],[1,3,4],[2],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        dist = [[float('inf')] * n for _ in range(n)] \n",
    "        for i in range(n):\n",
    "            dist[i][i] = 0 \n",
    "        for i in range(n):\n",
    "            for j in graph[i]:\n",
    "                dist[i][j] = dist[j][i] = 1 \n",
    "            \n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])\n",
    "        \n",
    "        dp = [[float('inf')] * (1 << n) for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            dp[i][1<<i] = 0 \n",
    "        for j in range(1, 1 << n):\n",
    "            for i in range(n):\n",
    "                if (j >> i) & 1 == 0:\n",
    "                    continue \n",
    "                for v in range(n):\n",
    "                    if (j >> v) & 1 and v != i:\n",
    "                        dp[i][j] = min(dp[i][j], dp[v][j^(1<<i)] + dist[v][i]) \n",
    "        ans = float('inf')\n",
    "        for i in range(n):\n",
    "            ans = min(ans, dp[i][(1<<n) - 1])\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\r\n",
    "        n=len(graph)\r\n",
    "        dist=[[n+1]*n for _ in range(n)]\r\n",
    "        for i in range(n):\r\n",
    "            for j in graph[i]:\r\n",
    "                dist[i][j]=dist[j][i]=1\r\n",
    "                # dist[i][j]=1\r\n",
    "        \r\n",
    "        for i in range(n):\r\n",
    "            for j in range(n):\r\n",
    "                for k in range(n):\r\n",
    "                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\r\n",
    "        \r\n",
    "        f=[[float('inf')]*(1<<n) for _ in range(n)]\r\n",
    "        for mask in range(1,1<<n):\r\n",
    "            if (mask & (mask-1))==0:\r\n",
    "                u=bin(mask).count('0')-1\r\n",
    "                f[u][mask]=0\r\n",
    "                continue\r\n",
    "            for u in range(n):\r\n",
    "                if mask & (1<<u)==0:\r\n",
    "                    continue\r\n",
    "                for v in range(n):\r\n",
    "                    if v==u or (mask & (1<<v)==0):\r\n",
    "                        continue\r\n",
    "                    f[u][mask]=min(f[u][mask],dist[v][u]+f[v][mask^(1<<u)])\r\n",
    "        return min(f[u][(1<<n)-1] for u in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        dist = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in graph[i]:\n",
    "                dist[i][j] = dist[j][i] = 1\n",
    "        # floyd\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n",
    "                    \n",
    "        # 状压dp: dp[state][i]: 状态为state, 所在位置为i的最短路径\n",
    "        dp = [[inf] * n for _ in range(1 << n)]\n",
    "        for i in range(n): dp[1 << i][i] = 0; # 每个点作为起点\n",
    "\n",
    "        for state in range(1 << n):\n",
    "            for i in range(n):\n",
    "                if state >> i & 1:\n",
    "                    for j in range(n):\n",
    "                        if not state >> j & 1:\n",
    "                            dp[state | (1 << j)][j] = min(dp[state | (1 << j)][j], dp[state][i] + dist[i][j])\n",
    "\n",
    "        return min(dp[(1 << n) - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        m = 1 << n\n",
    "        INF = int(1e9)\n",
    "        dp = [[INF for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            t = 1<<i\n",
    "            dp[t][i] = 0\n",
    "            q.append((t, i))\n",
    "        \n",
    "        while q:\n",
    "            t, i = q.pop()\n",
    "\n",
    "            for j in graph[i]:\n",
    "                tmp = t | (1 <<  j)\n",
    "                d = dp[t][i] + 1\n",
    "                if d < dp[tmp][j]:\n",
    "                    dp[tmp][j] = d\n",
    "                    q.append((tmp, j))\n",
    "        \n",
    "        res = INF\n",
    "        m -= 1\n",
    "        for i in range(n):\n",
    "            res = min(res, dp[m][i])\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        INF=0x3f3f3f3f\n",
    "        n=len(graph)\n",
    "        self.A=[[INF for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(0,n):    #建立邻接矩阵A\n",
    "            for j in graph[i]:self.A[i][j]=1\n",
    "        self.Floyd()\n",
    "        m=1<<n;           #总的状态数\n",
    "        dp=[[INF for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(0,n):dp[1<<i][i]=0\n",
    "        for state in range(0,m):     #枚举所有的state\n",
    "            for i in range(0,n):    #枚举state中已访问的i\n",
    "                if not self.inset(state,i):continue;  #i不在state中时跳过\n",
    "                for j in range(0,n):    #枚举state中尚未访问过的j\n",
    "                    if self.inset(state,j):continue  #j在state中时跳过\n",
    "                    state1=self.addj(state,j)\n",
    "                    dp[state1][j]=min(dp[state1][j],dp[state][i]+self.A[i][j])\n",
    "        return min(dp[m-1])\n",
    "    def inset(self,state,j):       #判断顶点j是否在state中\n",
    "    \treturn (state & (1<<j))!=0\n",
    "    def addj(self,state,j):       #在state添加顶点j\n",
    "   \t    return state | (1<<j)\n",
    "    def Floyd(self):\n",
    "        n=len(self.A)\n",
    "        for k in range(0,n):\n",
    "            for i in range(0,n):\n",
    "                for j in range(0,n):\n",
    "                    self.A[i][j]=min(self.A[i][j],self.A[i][k]+self.A[k][j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        min_res = -1\n",
    "\n",
    "        queue = []\n",
    "        met = [[False]*(1<<n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            queue.append((i,1<<i,0))\n",
    "            met[i][1<<i] = True\n",
    "\n",
    "        full = 2**n - 1\n",
    "        while queue:\n",
    "            x,s,d = queue[0]\n",
    "            queue.pop(0)\n",
    "            if s == full:\n",
    "                min_res = d\n",
    "                break\n",
    "            for y in graph[x]:\n",
    "                if met[y][s|(1<<y)] == False:\n",
    "                    met[y][s|(1<<y)]= True\n",
    "                    queue.append((y, s|(1<<y), d+1))\n",
    "        return min_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        min_res = -1\n",
    "        FULL = (1<<n) - 1\n",
    "        # met[x][s]表示 是否已经访问过 节点x在状态s的这一情况\n",
    "        # 然后以所有点作为起点做BFS, 只需要用met控制不要去重复访问状态, 就能算出最短距离\n",
    "        met = [[False]*(1<<n) for _ in range(n)]\n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            queue.append((i, 1<<i, 0))\n",
    "            met[i][1<<i] = True\n",
    "        while queue:\n",
    "            x,s,d = queue[0]\n",
    "            queue.pop(0)\n",
    "            if s==FULL:\n",
    "                min_res = d\n",
    "                break\n",
    "            for y in graph[x]:\n",
    "                if not met[y][s|(1<<y)]:\n",
    "                    met[y][s|(1<<y)] = True\n",
    "                    queue.append((y, s|(1<<y), d+1))\n",
    "        return min_res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        dp = [[-1] * n for _ in range(1 << n)]\n",
    "\n",
    "        queue = deque([(1 << i, i, 0) for i in range(n)])\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[1 << i][i] = 0\n",
    "\n",
    "        while queue:\n",
    "            mask, node, distance = queue.popleft()\n",
    "\n",
    "            if mask == (1 << n) - 1:\n",
    "                return distance\n",
    "            \n",
    "            for nei in graph[node]:\n",
    "                new_mask = mask | (1 << nei)\n",
    "\n",
    "                if dp[new_mask][nei] == -1:\n",
    "                    dp[new_mask][nei] = distance + 1\n",
    "                    queue.append((new_mask, nei, distance + 1))\n",
    "        return - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "    n=len(graph)                   #顶点个数\n",
    "    endstate=(1<<n)-1              #目标状态\n",
    "    visited=[[0 for _ in range(1<<n)] for _ in range(n)]\n",
    "    qu=deque()\n",
    "    for i in range(n):      #所有顶点及其初始状态进队\n",
    "      state=self.addj(0,i)\n",
    "      qu.append([i,state])\n",
    "      visited[i][state]=1\n",
    "    bestd=0\n",
    "    while qu:\n",
    "      cnt=len(qu)              #求队中元素个数\n",
    "      for i in range(0,cnt):      #处理该层的所有元素\n",
    "          [u,state]=qu.popleft()       #出队(u,state)\n",
    "          if state==endstate:            #第一次找到目标状态则返回\n",
    "            return bestd\n",
    "          for v in graph[u]:           #找u的所有相邻顶点v\n",
    "            state1=self.addj(state,v) #添加顶点v\n",
    "            if visited[v][state1]==1:  #已经访问则跳过\n",
    "              continue;\n",
    "            qu.append([v,state1])\n",
    "            visited[v][state1]=1\n",
    "      bestd+=1                          #搜索一层，路径长度增加1\n",
    "    return -1                            #没有找到目标状态返回-1\n",
    "  def addj(self,state,j):             #在state添加顶点j\n",
    "    return state | (1<<j)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        queue = []\n",
    "        vis = [[False for _ in range(1 << n)] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            queue.append([i, 1 << i])\n",
    "            vis[i][1 << i] = True\n",
    "        \n",
    "        step = 0\n",
    "        while queue:\n",
    "            next = []\n",
    "            for x, mask in queue:\n",
    "                if mask == (1 << n) - 1:\n",
    "                    return step\n",
    "                for y in graph[x]:\n",
    "                    nxt_mask = mask | (1 << y)\n",
    "                    if vis[y][nxt_mask]:\n",
    "                        continue\n",
    "                    vis[y][nxt_mask] = True\n",
    "                    next.append([y, nxt_mask])\n",
    "            queue = next\n",
    "            step += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        count_node = len(graph)\n",
    "        inf = 0x7fffffff\n",
    "        \n",
    "        # 邻接矩阵，用来进行后面的floyd算法\n",
    "        neighbor = [[inf if j!=i else 0 for j in range(count_node)] for i in range(count_node)]\n",
    "        for s,connection in enumerate(graph):\n",
    "            for d in connection:\n",
    "                neighbor[s][d] = 1\n",
    "                neighbor[d][s] = 1\n",
    "        # 进行Floyd算法，先遍历断点\n",
    "        for i in range(count_node):\n",
    "            for x in range(count_node):\n",
    "                for y in range(count_node):\n",
    "                    if neighbor[x][y] > neighbor[x][i] + neighbor[i][y]:\n",
    "                        neighbor[x][y] = neighbor[x][i] + neighbor[i][y]\n",
    "        #print(neighbor)\n",
    "        # 接下来开始进行广度优先遍历，每一个状态(dist, i, mask)表示当前位置在i，已经走了dist的距离，访问过mask的节点\n",
    "        q = Queue()\n",
    "        # 记录状态矩阵visited[i][mask]表示这个状态是否被访问过\n",
    "        visited = [[False for j in range(2**count_node)]for i in range(count_node)]\n",
    "        # 记录结果矩阵，表示某个状态最短距离\n",
    "        result = [[inf for j in range(2**count_node)]for i in range(count_node)]\n",
    "        # 初始状态\n",
    "        for i in range(count_node):\n",
    "            q.put((i, 0+2**i))\n",
    "            visited[i][2**i] = True\n",
    "            result[i][2**i] = 0\n",
    "        while not q.empty():\n",
    "            (cur_pos, cur_mask) = q.get()\n",
    "            #print(cur_pos, cur_mask)\n",
    "            # 开始考虑扩展\n",
    "            for i in range(count_node):\n",
    "                # 这个节点目前没有被访问过\n",
    "                # 更新其最短距离\n",
    "                if cur_mask & 2**i == 0:\n",
    "                    result[i][cur_mask+2**i] = min(result[i][cur_mask+2**i], result[cur_pos][cur_mask]+neighbor[cur_pos][i])\n",
    "                    if not visited[i][cur_mask+2**i]:\n",
    "                        q.put((i, cur_mask+2**i))\n",
    "                        visited[i][cur_mask+2**i]=True\n",
    "            #print(result)\n",
    "        return_result = inf\n",
    "        for i in range(count_node):\n",
    "            return_result = min(return_result, result[i][2**count_node-1])\n",
    "        return return_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        dist = [[n for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in graph[i]:\n",
    "                dist[i][j] = 1\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])\n",
    "        dp = [[float('inf') for _ in range(1 << n)] for _ in range(n)]\n",
    "        for mask in range(1, 1 << n):\n",
    "            if mask & (mask - 1) == 0: \n",
    "                cnt = bin(mask).count('0') - 1\n",
    "                dp[cnt][mask] = 0\n",
    "            else:\n",
    "                for u in range(n):\n",
    "                    if mask & (1 << u):\n",
    "                        for v in range(n):\n",
    "                            if mask & (1 << v) and u != v:\n",
    "                                dp[u][mask] = min(dp[u][mask], dp[v][mask ^ (1 << u)] + dist[u][v])\n",
    "        return min([dp[i][-1] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        dist = [[n for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in graph[i]:\n",
    "                dist[i][j] = 1\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])\n",
    "        dp = [[float('inf') for _ in range(1 << n)] for _ in range(n)]\n",
    "        for mask in range(1, 1 << n):\n",
    "            if mask & (mask - 1) == 0: \n",
    "                cnt = bin(mask).count('0') - 1\n",
    "                dp[cnt][mask] = 0\n",
    "            else:\n",
    "                for u in range(n):\n",
    "                    if mask & (1 << u):\n",
    "                        for v in range(n):\n",
    "                            if mask & (1 << v) and u != v:\n",
    "                                dp[u][mask] = min(dp[u][mask], dp[v][mask ^ (1 << u)] + dist[u][v])\n",
    "        return min([dp[i][-1] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        dp = [[n + 1 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in graph[i]:\n",
    "                dp[i][j] = 1\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n",
    "        dist = [[float('inf') for _ in range(1 << n)] for _ in range(n)]\n",
    "        for mask in range(1, 1 << n):\n",
    "            if (mask & (mask - 1)) == 0:\n",
    "                u = bin(mask).count('0') - 1\n",
    "                dist[u][mask] = 0\n",
    "            else:\n",
    "                for u in range(n):\n",
    "                    if mask & (1 << u):\n",
    "                        for v in range(n):\n",
    "                            if mask & (1 << v) and u != v:\n",
    "                                dist[u][mask] = min(dist[u][mask], dist[v][mask ^ (1 << u)] + dp[v][u])\n",
    "        return min([dist[i][(1 << n) - 1] for i in range(n)])\n",
    "        # n = len(graph)\n",
    "        # queue = collections.deque((i, 1 << i, 0) for i in range(n))\n",
    "        # sets = {(i, 1 <<i ) for i in range(n)}\n",
    "        # ans = 0\n",
    "        # while queue:\n",
    "        #     u, mask, dist = queue.popleft()\n",
    "        #     if mask == (1 << n) - 1:\n",
    "        #         ans = dist\n",
    "        #         break\n",
    "        #     for v in graph[u]:\n",
    "        #         mask_v = mask | (1 << v)\n",
    "        #         if (v, mask) not in sets:\n",
    "        #             queue.append((v, mask_v, dist + 1))\n",
    "        #             sets.add((v, mask_v))\n",
    "        # return ans\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1. Algo - 3 min\n",
    "2. Implementation - 10 min\n",
    "3. Wrong algorithm - 20 min. The DFS algorithm at the bottom doesn't work. Need to\n",
    "   use BFS to get the shortest path.\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        def bfs(start):\n",
    "            q, visited = deque(), set()\n",
    "            q.append((start, 1 << start, 0))\n",
    "            visited.add((start, 1 << start))\n",
    "            while q:\n",
    "                cur_node, cur_visited, cur_step = q.popleft()\n",
    "                if cur_visited == (1 << n) - 1: return cur_step\n",
    "                for nxt in graph[cur_node]:\n",
    "                    if (nxt, cur_visited | (1 << nxt)) not in visited:\n",
    "                        visited.add((nxt, cur_visited | (1 << nxt)))\n",
    "                        q.append((nxt, cur_visited | (1 << nxt), cur_step + 1))\n",
    "\n",
    "        n, result = len(graph), inf\n",
    "        for i in range(n):\n",
    "            result = min(result, bfs(i))\n",
    "        return result\n",
    "\n",
    "    # def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "    #     @cache\n",
    "    #     def dp(cur_node, visited):\n",
    "    #         if visited == (1 << n) - 1: return 0\n",
    "    #         states.add((cur_node, visited))\n",
    "    #         result = inf\n",
    "    #         for nxt in graph[cur_node]:\n",
    "    #             if (nxt, (visited | (1 << nxt))) not in states: # 1WA: missing this check\n",
    "    #                 result = min(result, 1 + dp(nxt, (visited | (1 << nxt))))\n",
    "    #         print(cur_node, \"{0:b}\".format(visited).zfill(n), result)\n",
    "    #         return result\n",
    "\n",
    "    #     n, result = len(graph), inf\n",
    "    #     for i in range(1):\n",
    "    #         states = set()\n",
    "    #         dp.cache_clear()\n",
    "    #         result = min(result, dp(i, 1 << i))\n",
    "    #         print(i, dp(i, 1 << i))\n",
    "    #     return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        m = (1 << n) - 1\n",
    "        def bfs(start):\n",
    "            ans = inf\n",
    "            mask = 1 << start\n",
    "            q = deque([(start, mask)])\n",
    "            vis = {(start, mask): 0}\n",
    "            while q:\n",
    "                p = q.popleft()\n",
    "                x, stat = p\n",
    "                if stat == m:\n",
    "                    ans = min(ans, vis[p])\n",
    "                    continue\n",
    "                for y in graph[x]:\n",
    "                    stat2 = stat | (1 << y)\n",
    "                    p2 = (y, stat2)\n",
    "                    if p2 in vis and vis[p2] <= vis[p] + 1:\n",
    "                        continue\n",
    "                    vis[p2] = vis[p] + 1\n",
    "                    q.append(p2)\n",
    "            return ans\n",
    "        return min(bfs(x) for x in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        queue = [pow(2, i)+(i<<n) for i in range(n)]\n",
    "        visited = set(queue)\n",
    "        count = 0\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                x = queue.pop(0)\n",
    "                if (x+1)%pow(2,n) == 0:\n",
    "                    return count\n",
    "                a = x\n",
    "                l = graph[a>>n]\n",
    "                for j in l:\n",
    "                    x = a\n",
    "                    if (x>>j)%2==0:\n",
    "                        x+=1<<j\n",
    "                        x = x%pow(2,n)+(j<<n)\n",
    "                        if x not in visited:\n",
    "                            queue.append(x)\n",
    "                            visited.add(x)\n",
    "                    else:\n",
    "                        x = x % pow(2, n) + (j<<n)\n",
    "                        if x not in visited:\n",
    "                            queue.append(x)\n",
    "                            visited.add(x)\n",
    "            count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n,deep=len(graph),0\n",
    "        target=(1<<n)-1\n",
    "        Q=deque((i<<n)|(1<<i) for i in range(n))\n",
    "        dp=set()\n",
    "        while Q:\n",
    "            deep+=1\n",
    "            for _ in range(len(Q)):\n",
    "                temp=Q.popleft()\n",
    "                x,bitMap=temp>>n,temp&target\n",
    "                for nx in graph[x]:\n",
    "                    if (temp:=bitMap|(1<<nx))==target:\n",
    "                        return deep\n",
    "                    if (next_state:=temp|(nx<<n)) not in dp:\n",
    "                        dp.add(next_state)\n",
    "                        Q.append(next_state)\n",
    "        return 0\n",
    "\n",
    "'''\n",
    "法二 bfs+dp+状态压缩\n",
    "使用一个n bit的bitMap，第i位为1表示第i个节点被走过了。\n",
    "显然我们不关心怎么走得，我们只关心这个状态能不能达到，以及达到的最少步数。\n",
    "\n",
    "可以使用bfs，这样搜索到答案，自动就是最少步数。\n",
    "然后要考虑的就是如何剪枝，重要的是如何定义状态\n",
    "（遇到的过状态我们可以直接pass，因为显然之前遇到相同状态的时候步数更少）\n",
    "而且我们并不考虑如何遍历这些点的，我们只在乎这些点有没有被遍历过。\n",
    "\n",
    "所以可以这样定义状态(当前位置,走过的点的bitMap)\n",
    "不论如何走出相同的bitMap，当前位置相同，就是同样的状态了。\n",
    "bitMap至多12bit，位置也可以用4bit表示，可以把它压缩成一个16bit的数\n",
    "\n",
    "\n",
    "\n",
    "法一 带状态的bfs\n",
    "使用set记录路径（因为是求最短路径长度，所以顺序什么的不用在意）\n",
    "\n",
    "考察反复横跳的问题，走过的点可以再走，但是走过的边没必要超过2次，每条边最多正向走一次，反向走一次\n",
    "需要对边的状态进行记录，需要使用状态压缩，边至多有12^2=144个可以用18B进行标记\n",
    "i~j的边用第i*12+j位标记\n",
    "超时\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n=len(graph)\n",
    "        target=(1<<n)-1\n",
    "        def bfs() -> int:\n",
    "            Q=deque([[i,1<<i,0] for i in range(n)])\n",
    "            Map=defaultdict(bool)\n",
    "            deep=0\n",
    "            while Q:\n",
    "                for _ in range(len(Q)):\n",
    "                    x,path,edge_state=Q.popleft()\n",
    "                    if path==target:\n",
    "                        return deep\n",
    "                    temp=(x<<3)+(x<<2)\n",
    "                    for nx in graph[x]:\n",
    "                        if (edge_state>>(temp+nx))&1:\n",
    "                            continue\n",
    "                        Q.append([nx,path|(1<<nx),edge_state^(1<<(temp+nx))])\n",
    "                deep+=1\n",
    "        \n",
    "        return bfs()\n",
    "\n",
    "[[]]\n",
    "[[1,2,3],[0],[0],[0]]\n",
    "[[1],[0,2,4],[1,3,4],[2],[1,2]]\n",
    "[[2,3],[2],[0,1,4],[0,4],[2,3]]\n",
    "[[1],[0,2,6],[1,3],[2],[5],[4,6],[1,5,7],[6]]\n",
    "[[1,4,6,8,9,10,11],[0,6],[9],[5],[0],[7,3],[0,1],[9,5],[0],[0,2,7],[0],[0]]\n",
    "[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11], [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11], [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11], [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11], [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11], [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11], [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11], [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        # 动规状压\n",
    "        # dp[(i,k)]表示 i表为二进制后 数位为1的节点所经 最后停于k 的最小长度\n",
    "        n = len(graph)\n",
    "        dp = defaultdict(lambda: -1)\n",
    "        dis = {}\n",
    "        for a in range(n):\n",
    "            dis[(a,a)] = 0\n",
    "            for b in range(a+1, n):\n",
    "                q = deque([(a,0)])\n",
    "                minn = 300\n",
    "                while q:\n",
    "                    p, t = q.popleft()\n",
    "                    if t > minn:\n",
    "                        continue\n",
    "                    for nxt in graph[p]:\n",
    "                        if nxt == b:\n",
    "                            minn = min(minn, t+1)\n",
    "                        else:\n",
    "                            q.append((nxt, t+1))\n",
    "                dis[(a,b)] = minn\n",
    "                dis[(b,a)] = minn\n",
    "        # print(dis)\n",
    "\n",
    "        for j in range(n):\n",
    "            dp[(1<<j, j)] = 1\n",
    "        for i in range(1 << n):\n",
    "            if i & (i-1) == 0:\n",
    "                continue\n",
    "            for k in range(n):\n",
    "                if i & (1<<k) != 0:\n",
    "                    pre = i - (1<<k)\n",
    "                    minn = 300\n",
    "                    for j in range(n):\n",
    "                        if ((1<<j) & pre) != 0:\n",
    "                            minn = min(minn, dp[(pre, j)] + dis[(j, k)])\n",
    "                    dp[(i, k)] = minn\n",
    "        \n",
    "        r = [dp[((1<<n)-1, i)] for i in range(n)]\n",
    "        return min(r)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef shortestPathLength(self, graph):\n",
    "\t\tn = len(graph)\n",
    "\t\tbegin = []\n",
    "\t\tout = n\n",
    "\t\tfor i, l in enumerate(graph):\n",
    "\t\t\tif len(l) == out:\n",
    "\t\t\t\tbegin.append(i)\n",
    "\t\t\telif len(l) < out:\n",
    "\t\t\t\tbegin = [i]\n",
    "\t\t\t\tout = len(l)\n",
    "\t\tmap1 = {}\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tvisited = {i}\n",
    "\t\t\tstack = {i}\n",
    "\t\t\tcur = 0\n",
    "\t\t\twhile stack:\n",
    "\t\t\t\tnxt = set()\n",
    "\t\t\t\tfor j in stack:\n",
    "\t\t\t\t\tmap1[(i, j)] = cur\n",
    "\t\t\t\t\tfor k in graph[j]:\n",
    "\t\t\t\t\t\tif k not in visited:\n",
    "\t\t\t\t\t\t\tnxt.add(k)\n",
    "\t\t\t\t\t\t\tvisited.add(k)\n",
    "\t\t\t\tstack = nxt\n",
    "\t\t\t\tcur += 1\n",
    "\t\tmap2 = {(i, tuple([i])): 0 for i in range(n)}\n",
    "\t\twhile True:\n",
    "\t\t\tmap0 = {}\n",
    "\t\t\tfor cur, visited in map2:\n",
    "\t\t\t\tfor i in range(n):\n",
    "\t\t\t\t\tif i not in visited:\n",
    "\t\t\t\t\t\tunion = tuple(set(visited).union({i}))\n",
    "\t\t\t\t\t\tmap0[(i, union)] = min(map0.get((i, union), float('inf')), map2[cur, visited] + map1[(cur, i)])\n",
    "\t\t\tif not map0:\n",
    "\t\t\t\tbreak\n",
    "\t\t\tmap2 = map0\n",
    "\t\tans = float('inf')\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tans = min(ans, map2[(i, tuple(range(n)))])\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# multisource bfs from each node, until all nodes are\r\n",
    "# visited. a node shouldn't be visited again with identical visiting status\r\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def shortestPathLength(self, graph: list[list[int]]) -> int:\r\n",
    "        n = len(graph)\r\n",
    "        visited: list[set[int]] = [set() for _ in range(n)]\r\n",
    "        q: deque[tuple[int, int, int]] = deque()\r\n",
    "        for i in range(n):\r\n",
    "            q.append((0, i, 1 << i))\r\n",
    "            visited[i].add(1 << i)\r\n",
    "        \r\n",
    "        while q:\r\n",
    "            l, node, stat = q.popleft()\r\n",
    "            if stat == (1 << n) - 1: return l\r\n",
    "            for nxt in graph[node]:\r\n",
    "                nstat = stat | (1 << nxt)\r\n",
    "                if nstat not in visited[nxt]:\r\n",
    "                    visited[nxt].add(nstat)\r\n",
    "                    q.append((l + 1, nxt, nstat))\r\n",
    "        \r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        dp = [defaultdict(lambda: 1e10) for _ in range(n)]\n",
    "        dq = deque()\n",
    "        visiting = set()\n",
    "        targetState = 0\n",
    "        for i in range(n):\n",
    "            dp[i][(0x01 << i)] = 0\n",
    "            dq.append((i, 0x01 << i))\n",
    "            visiting.add((i, (0x01 << i)))\n",
    "            targetState |= (0x01 << i)\n",
    "        while dq:\n",
    "            node, state = dq.popleft()\n",
    "            visiting.remove((node, state))\n",
    "            dis = dp[node][state]\n",
    "            for nextNode in graph[node]:\n",
    "                nextState = state | (0x01 << nextNode)\n",
    "                if nextState == targetState:\n",
    "                    return dis + 1\n",
    "                if dis + 1 < dp[nextNode][nextState]:\n",
    "                    dp[nextNode][nextState] = dis+1\n",
    "                    if (nextNode, nextState) not in visiting:\n",
    "                        visiting.add((nextNode, nextState))\n",
    "                        dq.append((nextNode, nextState))\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "      \n",
    "        n = len(graph)\n",
    "        d=defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                #step i-j\n",
    "                step=0\n",
    "                bfs=[i]\n",
    "                visit=set([i])\n",
    "                while j not in visit:\n",
    "                    step+=1\n",
    "                    newbfs=[]\n",
    "                    for p in bfs:\n",
    "                        for link in graph[p]:\n",
    "                            if link not in visit:\n",
    "                                visit.add(link)\n",
    "                                newbfs.append(link)\n",
    "                    bfs=newbfs\n",
    "                d[(i,j)]=step\n",
    "                d[(j,i)]=step\n",
    "        #cost,mask,current\n",
    "        dfs=[(0,1<<(n-1-x),x) for x in range(n)]\n",
    "        pre={}\n",
    "        res=(n-1)**2\n",
    "        while dfs:\n",
    "            cost,mask,current=dfs.pop()\n",
    "            if cost>=res:\n",
    "                continue\n",
    "            if mask==(1<<n)-1:\n",
    "                if cost<res:\n",
    "                    res=cost\n",
    "            else:\n",
    "                if (mask,current) in pre:\n",
    "                    if pre[(mask,current)]<=cost:\n",
    "                        continue\n",
    "                pre[(mask,current)]=cost\n",
    "                goon=False\n",
    "                for link in graph[current]:\n",
    "                    if mask&(1<<(n-1-link))==0:\n",
    "                        dfs.append((cost+1,mask^(1<<(n-1-link)),link))\n",
    "                        goon=True\n",
    "                if goon==False:\n",
    "                    for i in range(n):\n",
    "                        if mask&(1<<(n-1-i))==0:\n",
    "                            dfs.append((cost+d[(current,i)],mask^(1<<(n-1-i)),i))\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        sz = len(graph)\n",
    "        pq = []\n",
    "        target = (1 << sz) - 1\n",
    "        costs = {}\n",
    "\n",
    "        def distance(x):\n",
    "            return sz - bin(x).count('1')\n",
    "\n",
    "        for cur in range(sz):\n",
    "            pq.append((0 + distance(1 << cur), cur, 1 << cur))  # priority location state\n",
    "            costs[(cur, 1 << cur)] = 0\n",
    "        while pq:\n",
    "            _, cur, state = heapq.heappop(pq)\n",
    "            curCost = costs[(cur, state)]\n",
    "            if state == target:\n",
    "                return curCost\n",
    "            for nei in graph[cur]:\n",
    "                neiState = state | (1 << nei)\n",
    "                if (nei, neiState) not in costs:\n",
    "                    costs[(nei, neiState)] = curCost + 1\n",
    "                    priority = curCost + 1 + distance(neiState)\n",
    "                    heapq.heappush(pq, (priority, nei, neiState))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        dist = [{} for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dist[i][1<<i] = 0\n",
    "            for j in graph[i]:\n",
    "                dist[i][1 << j] = 1\n",
    "                dist[j][1 << i] = 1\n",
    "        mask = (1 << n) - 1\n",
    "        min_dist = n * n\n",
    "        for i in range(n):\n",
    "            self.search(i, mask ^ (1 << i), dist, graph)\n",
    "            #print(\"### i=\", i, \"dist=\", dist[i])\n",
    "            if min_dist > dist[i][mask ^ (1 << i)]:\n",
    "                min_dist = dist[i][mask ^ (1 << i)]\n",
    "\n",
    "        return min_dist\n",
    "\n",
    "    def search(self, start, target, dist, graph):\n",
    "        n = len(graph)\n",
    "        if target in dist[start]:\n",
    "            return dist[start][target]\n",
    "        dist[start][target] = n * n\n",
    "        for next_node in graph[start]:\n",
    "            next_target = target\n",
    "            if (target & (1 << next_node))  !=  0:\n",
    "                next_target = target ^ (1 << next_node)\n",
    "            self.search(next_node, next_target, dist, graph)\n",
    "            #print(\"start=\", start, \"next=\",next_node, \"next_target=\", next_target, \"target=\", target)\n",
    "            #print(\"dist=\", dist[next_node])\n",
    "            for next_next_target in dist[next_node]:\n",
    "                new_target = (1 << next_node) | next_next_target\n",
    "                if new_target not in dist[start] or dist[start][new_target] > dist[next_node][next_next_target] + 1:\n",
    "                    dist[start][new_target] = dist[next_node][next_next_target] + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        # 初始以每个点为起点\n",
    "        frontier = [(i, 1 << i) for i in range(n)]\n",
    "        explored = set(frontier)\n",
    "        # 目标为2^n - 1\n",
    "        goal = (1 << n) - 1\n",
    "        step = 0\n",
    "        while frontier:\n",
    "            nxt = []\n",
    "            for cur, state in frontier:\n",
    "                if state == goal:\n",
    "                    return step\n",
    "                for other in graph[cur]:\n",
    "                    # 下一个状态\n",
    "                    successor = (other, 1 << other | state)\n",
    "                    # 新的状态没有被走过\n",
    "                    if successor not in explored:\n",
    "                        explored.add(successor)\n",
    "                        nxt.append(successor)\n",
    "            frontier = nxt\n",
    "            step += 1\n",
    "        # 图不连通\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        - build the queue for BFS\n",
    "            - starting at every node\n",
    "            - (node,seen_state)\n",
    "        \"\"\"\n",
    "        queue = collections.deque([])\n",
    "        n = len(graph)\n",
    "        seen = set()\n",
    "        \n",
    "        for node in range(n):\n",
    "            # using the bit at the location node to indicate\n",
    "            # that node is visited\n",
    "            visited_states = 1 << node\n",
    "            queue.append((node,visited_states))\n",
    "            seen.add((node,visited_states))\n",
    "        \n",
    "        step = 0\n",
    "        complete_state = (1 << n) - 1\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur,seen_states = queue.popleft()\n",
    "                if seen_states == complete_state:\n",
    "                    return step\n",
    "                \n",
    "                for nxt in graph[cur]:\n",
    "                    # mark the new state as visisted\n",
    "                    new_states = seen_states | (1 << nxt)\n",
    "                    if (nxt,new_states) not in seen:\n",
    "                        seen.add((nxt,new_states))\n",
    "                        queue.append((nxt,new_states))\n",
    "            step +=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        queue = collections.deque((i, 1 << i, 0) for i in range(n))\n",
    "        seen = {(i, 1 << i) for i in range(n)}\n",
    "\n",
    "        while queue:\n",
    "            i, mask, dist = queue.popleft()\n",
    "            if mask == (1 << n) - 1:\n",
    "                return dist\n",
    "            for j in graph[i]:\n",
    "                m = mask | (1 << j)\n",
    "                if (j, m) not in seen:\n",
    "                    queue.append((j, m, dist + 1))\n",
    "                    seen.add((j, m))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        dis = [[n] * n for _ in range(n)]\n",
    "        for i, l in enumerate(graph):\n",
    "            dis[i][i] = 0\n",
    "            for j in l:\n",
    "                dis[i][j] = dis[j][i] = 1\n",
    "        for w in range(n):\n",
    "            for u in range(n):\n",
    "                for v in range(n):\n",
    "                    dis[u][v] = min(dis[u][v], dis[u][w] + dis[w][v])\n",
    "        inf = n * n\n",
    "        dp = [[inf] * n for _ in range(1 << n)]\n",
    "        def dfs(i, s):\n",
    "            if i == 1 << s:\n",
    "                return 0\n",
    "            if dp[i][s] != inf:\n",
    "                return dp[i][s]\n",
    "            ni = i ^ (1 << s)\n",
    "            for j in range(n):\n",
    "                if ni >> j & 1:\n",
    "                    dp[i][s] = min(dp[i][s], dis[s][j] + dfs(ni, j))\n",
    "            return dp[i][s]\n",
    "\n",
    "        return min(dfs((1 << n) - 1, i) for i in range(n))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "\n",
    "        # 1.初始化队列及标记数组，存入起点\n",
    "        q = deque((i, 1 << i, 0) for i in range(n)) # 三个属性分别为 idx, mask, dist；存入起点，起始距离0，标记\n",
    "        vis = {(i, 1 << i) for i in range(n)} # 节点编号及当前状态\n",
    "        \n",
    "        # 开始搜索\n",
    "        while q:\n",
    "            u, mask, dist = q.popleft() # 弹出队头元素\n",
    "            if mask == (1 << n) - 1: # 找到答案，返回结果\n",
    "                return dist\n",
    "            # 扩展\n",
    "            for x in graph[u]:\n",
    "                nextmask = mask | (1 << x)\n",
    "                if (x, nextmask) not in vis:\n",
    "                    q.append((x, nextmask, dist + 1))\n",
    "                    vis.add((x, nextmask))\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        q = [(i, 1 << i) for i in range(n)]\n",
    "        went=set(q)\n",
    "        goal = (1 << n) - 1\n",
    "        #step记录BFS的轮数，同时结束时step的大小就是最短路径\n",
    "        step=0\n",
    "        while q:\n",
    "            record=[]\n",
    "            for u,mask in q:\n",
    "                if mask == goal:\n",
    "                    return step\n",
    "                # 搜索相邻的节点\n",
    "                for v in graph[u]:\n",
    "                    # 将 mask 的第 v 位置为 1\n",
    "                    mask_v = mask | (1 << v)\n",
    "                    if (v, mask_v) not in went:\n",
    "                        #由于for迭代q中不能为q添加元素\n",
    "                        record.append((v, mask_v))\n",
    "                        went.add((v, mask_v))\n",
    "            q=record\n",
    "            step+=1\n",
    "        #不连通\n",
    "        return -1   \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        q = [(i, 1 << i) for i in range(n)]\n",
    "        went=set(q)\n",
    "        goal = (1 << n) - 1\n",
    "        #step记录BFS的轮数，同时结束时step的大小就是最短路径\n",
    "        step=0\n",
    "        while q:\n",
    "            record=[]\n",
    "            for u,mask in q:\n",
    "                if mask == goal:\n",
    "                    return step\n",
    "                # 搜索相邻的节点\n",
    "                for v in graph[u]:\n",
    "                    # 将 mask 的第 v 位置为 1\n",
    "                    mask_v=mask | (1 << v)\n",
    "                    if (v,mask_v) not in went:\n",
    "                        #由于for迭代q中不能为q添加元素\n",
    "                        record.append((v, mask_v))\n",
    "                        went.add((v, mask_v))\n",
    "            q=record\n",
    "            step+=1\n",
    "        #不连通\n",
    "        return -1   \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        q = ((i, 1 << i) for i in range(n))\n",
    "        seen = {(i, 1 << i) for i in range(n)}\n",
    "        ans = 0\n",
    "        #step记录BFS的轮数，同时结束时step的大小就是最短路径\n",
    "        step=0\n",
    "        while q:\n",
    "            record=[]\n",
    "            for u,mask in q:\n",
    "                if mask == (1 << n) - 1:\n",
    "                    return step\n",
    "                # 搜索相邻的节点\n",
    "                for v in graph[u]:\n",
    "                    # 将 mask 的第 v 位置为 1\n",
    "                    mask_v = mask | (1 << v)\n",
    "                    if (v, mask_v) not in seen:\n",
    "                        #由于for迭代q中不能为q添加元素\n",
    "                        record.append((v, mask_v))\n",
    "                        seen.add((v, mask_v))\n",
    "            q=record\n",
    "            step+=1\n",
    "        #不连通\n",
    "        return -1   \n",
    "       \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        # 初始以每个点为起点\n",
    "        frontier = [(i, 1 << i) for i in range(n)]\n",
    "        explored = set(frontier)\n",
    "        # 目标为2^n - 1\n",
    "        goal = (1 << n) - 1\n",
    "        step = 0\n",
    "        while frontier:\n",
    "            nxt = []\n",
    "            for cur, state in frontier:\n",
    "                if state == goal:\n",
    "                    return step\n",
    "                for other in graph[cur]:\n",
    "                    # 下一个状态\n",
    "                    successor = (other, 1 << other | state)\n",
    "                    # 新的状态没有被走过\n",
    "                    if successor not in explored:\n",
    "                        explored.add(successor)\n",
    "                        nxt.append(successor)\n",
    "            frontier = nxt\n",
    "            step += 1\n",
    "        # 图不连通\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n=len(graph)\n",
    "        d=[(i,1<<i,0) for i in range(n)]\n",
    "        v={(i,1<<i) for i in range(n)}\n",
    "        for i in range(n):\n",
    "            d.append((i,1<<i,0))\n",
    "        while d:\n",
    "            u,mask,dist=d.pop(0)\n",
    "            if mask==((1<<n)-1):\n",
    "                return dist\n",
    "            for j in graph[u]:\n",
    "                nexmask=mask|(1<<j)\n",
    "                if (j,nexmask) not in v:\n",
    "                    d.append((j,nexmask,dist+1))\n",
    "                    v.add((j,nexmask))        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        n=len(graph)\n",
    "        #BFS队列\n",
    "        d=[(i,1<<i,0) for i in range(n)]\n",
    "        #存储已经遍历过的节点\n",
    "        v=set()\n",
    "        for i in range(n):\n",
    "            d.append((i,1<<i,0))\n",
    "        while d:\n",
    "            u,mask,dist=d.pop(0)\n",
    "            if mask==((1<<n)-1):\n",
    "                return dist\n",
    "            for j in graph[u]:\n",
    "                nexmask=mask|(1<<j)\n",
    "                if (j,nexmask) not in v:\n",
    "                    d.append((j,nexmask,dist+1))\n",
    "                    v.add((j,nexmask))        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        TSP问题：多源BFS解决\n",
    "        利用一个整型mask来记录那些结点被访问过\n",
    "        从每个结点开始进行搜索，记录三个状态(idx,mask,dist)\n",
    "        \"\"\"\n",
    "        n = len(graph)\n",
    "        q = deque([(i,1<<i,0) for i in range(n)])\n",
    "        seen = {(i, 1 << i) for i in range(n)} # 节点编号及当前状态 为什么要一起保存 因为如果保存mask那么 a到b和b到a都是一样的 但这两个是两种情况\n",
    "        finishMask = (1<<n)-1 #结束时的mask\n",
    "        while q:\n",
    "            idx,mask,dist = q.popleft()\n",
    "            if mask==finishMask:\n",
    "                return dist\n",
    "            for neighbor in graph[idx]:\n",
    "                newMask = mask|1<<neighbor\n",
    "                if (neighbor,newMask) not in seen:\n",
    "                    q.append((neighbor,newMask,dist+1))\n",
    "                    seen.add((neighbor,newMask))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        q = deque((i, 1 << i, 0) for i in range(n))\n",
    "        seen = {(i, 1 << i) for i in range(n)}\n",
    "        ans = 0\n",
    "        \n",
    "        while q:\n",
    "            u, mask, dist = q.popleft()\n",
    "            if mask == (1 << n) - 1:\n",
    "                ans = dist\n",
    "                break\n",
    "            # 搜索相邻的节点\n",
    "            for v in graph[u]:\n",
    "                # 将 mask 的第 v 位置为 1\n",
    "                mask_v = mask | (1 << v)\n",
    "                if (v, mask_v) not in seen:\n",
    "                    q.append((v, mask_v, dist + 1))\n",
    "                    seen.add((v, mask_v))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,deque\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for i,neighbors in enumerate(graph):\n",
    "            adj[i] = set(neighbors)\n",
    "        all_visited = 2**len(graph)-1\n",
    "        q = deque()\n",
    "        visited = set()\n",
    "        for i in range(len(graph)):\n",
    "            q.append((i,1<<i,0))\n",
    "            visited.add((i,1<<i))\n",
    "        while q:\n",
    "            node,mask,dist = q.popleft()\n",
    "            for neighbor in adj[node]:\n",
    "                if (neighbor,mask|(1<<neighbor)) not in visited:\n",
    "                    if mask|(1<<neighbor) == all_visited: return dist+1\n",
    "                    q.append((neighbor,mask|(1<<neighbor),dist+1))\n",
    "                    visited.add((neighbor,mask|(1<<neighbor)))\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n=len(graph)\n",
    "        q=[]\n",
    "        seen=set()\n",
    "        for i in range(n):\n",
    "            q.append((i,1<<i,0))\n",
    "            seen.add((i,1<<i))\n",
    "        for i,mask,cnt in q:\n",
    "            if mask==(1<<n)-1:return cnt\n",
    "            for j in graph[i]:\n",
    "                newmask=mask |(1<<j)\n",
    "                if (j,newmask) not in seen:\n",
    "                    q.append((j,newmask,cnt+1))\n",
    "                    seen.add((j,newmask))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)  # 0<= i <= n-1\n",
    "        # 初始化\n",
    "        q = deque((i, 1<<i , 0) for i in range(n))  # 元素为(i, mask, dist)\n",
    "        vis = {(i, 1<<i) for i in range(n)}           # 访问各节点时的状态(i, mask)\n",
    "        while q:\n",
    "            i, mask, dist = q.popleft()\n",
    "            if mask == (1 <<n) -1:\n",
    "                return dist\n",
    "            # 下面对其状态进行扩展\n",
    "            for j in graph[i]:\n",
    "                if (j, mask) not in vis:\n",
    "                    q.append((j, mask | (1 << j), dist+1))\n",
    "                    vis.add((j, mask))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        queue = collections.deque([(0,i,1<<i) for i in range(n)])\n",
    "        dic = {(i,1<<i) for i in range(n)}\n",
    "        while queue:\n",
    "            step,i,vis = queue.popleft()\n",
    "            if vis == 2**n-1:\n",
    "                return step\n",
    "            for j in graph[i]:\n",
    "                if (j,vis) not in dic:\n",
    "                    dic.add((j,vis))\n",
    "                    queue.append((step+1,j,vis|(1<<j)))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestPathLength(self, graph):\n",
    "        n = len(graph)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        now = {(1 << i, i) for i in range(n)}\n",
    "        a_set = {(1 << i, i) for i in range(n)}\n",
    "        dist = 0\n",
    "        while True:\n",
    "            dist += 1\n",
    "            next_set = set()\n",
    "            for val, node in now:\n",
    "                for v in graph[node]:\n",
    "                    next_val = val | (1 << v)\n",
    "                    if next_val == (1 << n) - 1:\n",
    "                        return dist\n",
    "                    if (next_val, v) not in a_set:\n",
    "                        a_set.add((next_val, v))\n",
    "                        next_set.add((next_val, v))\n",
    "            now = next_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        queue = deque()\n",
    "        vis = [[False] * (1 << n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            queue.append((1 << i, i))\n",
    "        step = 0\n",
    "        target = (1 << n) - 1\n",
    "        while queue:\n",
    "            sz = len(queue)\n",
    "            for _ in range(sz):\n",
    "                state, idx = queue.popleft()\n",
    "                if state == target:\n",
    "                    return step\n",
    "                if vis[idx][state]:\n",
    "                    continue\n",
    "                vis[idx][state] = True\n",
    "                for neigh in graph[idx]:\n",
    "                    queue.append((state | (1 << neigh), neigh))\n",
    "            step += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        queue = deque()\n",
    "        vis = [[False] * (1 << n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            queue.append((1 << i, i))\n",
    "        step = 0\n",
    "        target = (1 << n) - 1\n",
    "        while queue:\n",
    "            sz = len(queue)\n",
    "            for _ in range(sz):\n",
    "                state, idx = queue.popleft()\n",
    "                if state == target:\n",
    "                    return step\n",
    "                # 当前状态被访问过了，那么现在再访问，step一定多于之前\n",
    "                if vis[idx][state]:\n",
    "                    continue\n",
    "                vis[idx][state] = True\n",
    "                for neigh in graph[idx]:\n",
    "                    queue.append((state | (1 << neigh), neigh))\n",
    "            step += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        N = len(graph)\n",
    "        que = collections.deque()\n",
    "        step = 0\n",
    "        goal = (1<<N) -1\n",
    "        visited = [[0 for j in range(1<<N)] for i in range(N)]\n",
    "        for i in range(N):\n",
    "            que.append((i,1<<i))\n",
    "\n",
    "        while que:\n",
    "            s = len(que)\n",
    "            for i in range(s):\n",
    "                node, state = que.popleft()\n",
    "                if state == goal:\n",
    "                    return step\n",
    "                if visited [node][state]:\n",
    "                    continue\n",
    "                visited[node][state] =1\n",
    "                for nextNode in graph[node]:\n",
    "                    que.append((nextNode, state|(1<<nextNode)))\n",
    "            step+=1\n",
    "        return step\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        q = [(i, 1 << i, 0) for i in range(n)]\n",
    "        s = set((i, 1 << i) for i in range(n))\n",
    "        mask = (1<<n) - 1\n",
    "        for u, m, d in q:\n",
    "            if m == mask:\n",
    "                return d\n",
    "            for v in graph[u]:\n",
    "                mm = m | (1<<v)\n",
    "                if (v,mm) in s:\n",
    "                    continue\n",
    "                q.append((v,mm,d+1))\n",
    "                s.add((v,mm))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(graph)\n",
    "\n",
    "#        queue = []\n",
    "        queue = collections.deque([])\n",
    "        tmp = [0] * n\n",
    "        for i in range(n):\n",
    "            tmp[i] = 1                  # 其实这个tmp和1<<i表示的是完全相同的状态\n",
    "            queue.append((i, tuple(tmp)))\n",
    "            tmp[i] = 0\n",
    "#        print(queue)\n",
    "        hashset = set(queue)        # 必须 tuple 因为 list 是 unhashable\n",
    "#        print(hashset)\n",
    "\n",
    "#[(0, (1, 0, 0, 0)), (1, (0, 1, 0, 0)), (2, (0, 0, 1, 0)), (3, (0, 0, 0, 1))]\n",
    "#{(1, (0, 1, 0, 0)), (2, (0, 0, 1, 0)), (0, (1, 0, 0, 0)), (3, (0, 0, 0, 1))}\n",
    "\n",
    "        goal = tuple([1] * n)     # (1, 1, 1, 1)\n",
    "  #      print(goal)\n",
    "\n",
    "        step = 0\n",
    "        while queue:\n",
    "            level = []\n",
    "#[(0, (1, 0, 0, 0)), (1, (0, 1, 0, 0)), (2, (0, 0, 1, 0)), (3, (0, 0, 0, 1))]\n",
    "       #     print('->', queue)\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "\n",
    "                node, state = queue.popleft()\n",
    "\n",
    "                if all(state):\n",
    "                    return step\n",
    "\n",
    "                for nb in graph[node]:\n",
    "\n",
    "                    tmp = list(state)\n",
    "                    tmp[nb] = 1\n",
    "\n",
    "                    successor = (nb, tuple(tmp))\n",
    "\n",
    "                    if successor not in hashset:\n",
    "                        hashset.add(successor)\n",
    "                        queue.append(successor)\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return -1       # 图不连通\n",
    "\n",
    "'''\n",
    "            for node, state in queue:\n",
    "                if all(state):\n",
    "                    return step\n",
    "\n",
    "                for nb in graph[node]:\n",
    "\n",
    "                    tmp = list(state)   # 把一个tuple再转换成list，实际上也进行了复制\n",
    "                    tmp[nb] = 1         # 这就相当于 1 << other | state\n",
    "\n",
    "                    successor = (nb, tuple(tmp))# 将list转换成tuple这样hash判断有没有走过\n",
    "\n",
    "                    if successor not in hashset:\n",
    "                        hashset.add(successor)\n",
    "                        level.append(successor)\n",
    "\n",
    "            queue = level\n",
    "            step += 1\n",
    "\n",
    "\n",
    "python按位运算是把数字看作二进制来进行计算的\n",
    "| 在python中 是指 或 运算\n",
    "<<: 左边的数字（二进制）左移多少位\n",
    ">>: 左边的数字（二进制）右移多少位\n",
    "\n",
    "\n",
    "不会状态压缩也没有关系，利用Py的tuple记录走过的状态也可以，效果和二进制一样的，只是效率没那么高，但是通俗易懂（保证看得懂）。\n",
    "\n",
    "BFS初始起点从每个点开始，我们第一次走到终点的时候，所用的距离就是最终答案。\n",
    "\n",
    "\n",
    "链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/solution/python-zhuang-tai-ya-suo-bfs-by-qubenhao-wkdy/\n",
    "        \n",
    "    \n",
    "旅行问题\n",
    "给定一系列城市 和 每对城市间距离, 求解访问每座城市一次 并 回到起始城市的最短回路\n",
    "在图论中, 这实质是在带权无向图中, 找权值最小的哈密顿回路\n",
    "\n",
    "\n",
    "本题是一道类似旅行商问题，区别在于：可以重复访问某些节点，且在遍历完最后一个节点后不用回到出发点\n",
    "\n",
    "\n",
    "https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/solution/gtalgorithm-tu-jie-fa-ba-hardbian-cheng-v5knb/\n",
    "\n",
    "\n",
    "\n",
    "跟另个graph题比, 这题不是一笔画问题, 一个node能重复visit, 这题做完后, 把那个一笔画题再拿出来看, 对比\n",
    "        \n",
    "多源bfs+位图记录每一条走过的路径，当有一条路径经过所有点时最短路径找到\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        items = {(1 << i, i) for i in range(n)}\n",
    "        seen = set()\n",
    "        loop = 0\n",
    "        while items:\n",
    "            next_items = set()\n",
    "            for item in items:\n",
    "                if item in seen:\n",
    "                    continue\n",
    "                seen.add(item)\n",
    "                mask, node = item\n",
    "                if mask == (2 ** n) - 1:\n",
    "                    return loop\n",
    "                for next_node in graph[node]:\n",
    "                    next_items.add((mask | (1 << next_node), next_node))\n",
    "            items = next_items\n",
    "            loop += 1\n",
    "        raise Exception('Unable to arrive all nodes')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        visited = set()\n",
    "        n = len(graph)\n",
    "        goal = [1 for _ in range(n)]\n",
    "        goal = tuple(goal)\n",
    "\n",
    "        from collections import deque\n",
    "\n",
    "        que = deque()\n",
    "        for i in range(n):\n",
    "            temp = [0 for _ in range(n)]\n",
    "            temp[i] = 1\n",
    "            que.append((i, tuple(temp)))\n",
    "            visited.add((i, tuple(temp)))\n",
    "        \n",
    "        step = 0\n",
    "        while que:\n",
    "            total = len(que)\n",
    "            for _ in range(total):\n",
    "                cur, trace = que.popleft()\n",
    "                if trace == goal:\n",
    "                    return step\n",
    "                for dst in graph[cur]:\n",
    "                    temp = list(trace)\n",
    "                    temp[dst] = 1\n",
    "                    newNext = (dst, tuple(temp))\n",
    "                    if newNext not in visited:\n",
    "                        visited.add(newNext)\n",
    "                        que.append(newNext)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        frontier = []\n",
    "        temp = [0] * n\n",
    "        for i in range(n):\n",
    "            temp[i] = 1\n",
    "            # 其实这个temp和1<<i表示的是完全相同的状态\n",
    "            frontier.append((i, tuple(temp)))\n",
    "            temp[i] = 0\n",
    "        # 必须是tuple因为list是属于unhashable的\n",
    "        explored = set(frontier)\n",
    "        goal = tuple([1] * n)\n",
    "        step = 0\n",
    "        while frontier:\n",
    "            nxt = []\n",
    "            for cur, state in frontier:\n",
    "                if state == goal:\n",
    "                    return step\n",
    "                for other in graph[cur]:\n",
    "                    # 把一个tuple再转换成list，实际上也进行了复制\n",
    "                    temp = list(state)\n",
    "                    # 这就相当于 1 << other | state\n",
    "                    temp[other] = 1\n",
    "                    # 将list转换成tuple，这样可以hash判断有没有走过\n",
    "                    successor = (other, tuple(temp))\n",
    "                    if successor not in explored:\n",
    "                        explored.add(successor)\n",
    "                        nxt.append(successor)\n",
    "            frontier = nxt\n",
    "            step += 1\n",
    "        # 图不连通\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n=len(graph)\n",
    "        pres={}\n",
    "        target=(1<<n)-1\n",
    "        tmpmin=0\n",
    "        def dfs(active,cur,distacne):\n",
    "            nonlocal pres,tmpmin\n",
    "            #print(cur)\n",
    "            #if distacne==0:\n",
    "            #    pres.clear()\n",
    "            if distacne>=tmpmin>0:\n",
    "                return\n",
    "            \n",
    "            if (active,cur) in pres and distacne>=pres[(active,cur)]:\n",
    "                return\n",
    "            pres[(active,cur)]=distacne\n",
    "\n",
    "            if active==target:\n",
    "                if tmpmin==0 or tmpmin>distacne:\n",
    "                    tmpmin=distacne\n",
    "                #print(tmpmin)\n",
    "                return\n",
    "\n",
    "            for nextpoint in graph[cur]:\n",
    "                newactive=active\n",
    "                if (newactive>>nextpoint &1)==0:\n",
    "                    newactive |= (1<<nextpoint)\n",
    "                if (newactive,nextpoint) not in pres or distacne+1<pres[(newactive,nextpoint)]:\n",
    "                    dfs(newactive,nextpoint,distacne+1)\n",
    "        idx=[]\n",
    "        for i in range(n):\n",
    "            if len(graph[i])==1:\n",
    "                idx.append(i)\n",
    "        if idx==[]:\n",
    "            idx=[i for i in range(n)]\n",
    "\n",
    "        for i in idx:\n",
    "            dfs(1<<i,i,0)\n",
    "            print(i,tmpmin)\n",
    "        return tmpmin\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        s = (1<<n) - 1\n",
    "        self.ans = inf\n",
    "        vis = {}\n",
    "        def dfs(cur, state, d):\n",
    "            # print(cur, state, d, self.ans)\n",
    "            if d >= self.ans:\n",
    "                return\n",
    "            \n",
    "            if state == 0:\n",
    "                self.ans = d\n",
    "                return\n",
    "            \n",
    "            if (cur, state) in vis:\n",
    "                if d >= vis[(cur, state)]:\n",
    "                    return\n",
    "                \n",
    "            vis[(cur, state)] = d\n",
    "            for j in graph[cur]:\n",
    "                t = 1<<j\n",
    "                if t & state:\n",
    "                    dfs(j, state ^ t, d + 1)\n",
    "                else:\n",
    "                    dfs(j, state, d + 1)\n",
    "        for i in range(n):\n",
    "            dfs(i, s ^ (1<<i), 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n=len(graph)\n",
    "        pres={}\n",
    "        target=(1<<n)-1\n",
    "        tmpmin=0\n",
    "        def dfs(active,cur,distacne):\n",
    "            nonlocal pres,tmpmin\n",
    "            #print(cur)\n",
    "            #if distacne==0:\n",
    "            #    pres.clear()\n",
    "            if distacne>=tmpmin>0:\n",
    "                return\n",
    "            \n",
    "            if (active,cur) in pres and distacne>=pres[(active,cur)]:\n",
    "                return\n",
    "            pres[(active,cur)]=distacne\n",
    "\n",
    "            if active==target:\n",
    "                if tmpmin==0 or tmpmin>distacne:\n",
    "                    tmpmin=distacne\n",
    "                #print(tmpmin)\n",
    "                return\n",
    "\n",
    "            for nextpoint in graph[cur]:\n",
    "                newactive=active\n",
    "                if (newactive>>nextpoint &1)==0:\n",
    "                    newactive |= (1<<nextpoint)\n",
    "                if (newactive,nextpoint) not in pres or distacne+1<pres[(newactive,nextpoint)]:\n",
    "                    dfs(newactive,nextpoint,distacne+1)\n",
    "        idx=[]\n",
    "        for i in range(n):\n",
    "            if len(graph[i])==1:\n",
    "                idx.append(i)\n",
    "        if idx==[]:\n",
    "            idx=[i for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(1<<i,i,0)\n",
    "            print(i,tmpmin)\n",
    "        return tmpmin\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n=len(graph)\n",
    "        pathd={}\n",
    "        paths=set()\n",
    "        vl=[]\n",
    "        for i in range(n):\n",
    "            p=2**i\n",
    "            pathd[(p,i)]=0\n",
    "            paths.add((p,i))\n",
    "            vl.append((p,i))\n",
    "        while vl:\n",
    "            t=vl.pop(0)\n",
    "            for i in range(len(graph[t[1]])):\n",
    "                q=graph[t[1]][i]\n",
    "                p=(2**q)|t[0]\n",
    "                if p==2**n-1:\n",
    "                    return pathd[t]+1\n",
    "                if (p,q) in paths:\n",
    "                    continue\n",
    "                paths.add((p,q))\n",
    "                pathd[(p,q)]=pathd[t]+1\n",
    "                vl.append((p,q))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        target = (1<<n) - 1\n",
    "        self.ans = inf\n",
    "        vis = {}\n",
    "        def dfs(cur, state, d):\n",
    "            # print(cur, state, d, self.ans)\n",
    "            if d >= self.ans:\n",
    "                return\n",
    "            \n",
    "            if state == target:\n",
    "                self.ans = d\n",
    "                return\n",
    "            \n",
    "            if (cur, state) in vis:\n",
    "                if d >= vis[(cur, state)]:\n",
    "                    return\n",
    "                \n",
    "            vis[(cur, state)] = d\n",
    "            for j in graph[cur]:\n",
    "                t = 1<<j\n",
    "                dfs(j, state | t, d + 1)\n",
    "        for i in range(n):\n",
    "            dfs(i, (1<<i), 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n=len(graph)\n",
    "        q=deque((i, 1 << i, 0) for i in range(n))\n",
    "\n",
    "        vis=set()\n",
    "        ALL_VIS=(1<<n)-1\n",
    "        while q:\n",
    "            i,mask,dis=q.popleft()\n",
    "            if (i,mask) in vis:\n",
    "                continue\n",
    "            vis.add((i,mask))\n",
    "            if mask==ALL_VIS:\n",
    "                return dis\n",
    "            for j in graph[i]:\n",
    "                new_mask=mask|(1<<j)\n",
    "                if (j,new_mask) not in vis:\n",
    "                    q.append((j,new_mask,dis+1))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, g: List[List[int]]) -> int:\n",
    "        res, n = inf, len(g)\n",
    "        q, mask = deque(), (1 << n) - 1\n",
    "        vis = defaultdict(set)\n",
    "        for i in range(n): q.append((1 << i, i, 0))\n",
    "        while q:\n",
    "            msk, u, d = q.popleft()\n",
    "            if msk == mask: res = min(res, d)\n",
    "            if d >= res or msk in vis[u]: continue\n",
    "            vis[u].add(msk)\n",
    "            for v in g[u]:\n",
    "                q.append((msk | (1 << v), v, d + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        sz = len(graph)\n",
    "        pq = []\n",
    "        best = set()\n",
    "        costs = {}\n",
    "        target = (1 << sz) - 1\n",
    "        for i in range(sz):\n",
    "            heapq.heappush(pq, (sz - 1, 0, i, 1 << i))\n",
    "            costs[(i, 1 << i)] = 0\n",
    "\n",
    "        def distance(state):\n",
    "            return sz - bin(state).count('1')\n",
    "\n",
    "        while pq:\n",
    "            _, step, cur, state = heapq.heappop(pq)\n",
    "            if state == target:\n",
    "                return step\n",
    "            best.add((cur, state))\n",
    "            for nei in graph[cur]:\n",
    "                if nei not in best:\n",
    "                    neiState = state | (1 << nei)\n",
    "                    if (nei, neiState) not in costs or step + 1 < costs[(nei, neiState)]:\n",
    "                        costs[(nei, neiState)] = step + 1\n",
    "                        priority = step + 1 + distance(neiState)\n",
    "                        heapq.heappush(pq, (priority, step + 1, nei, neiState))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        min_degree = 13\n",
    "        min_degree_index = []\n",
    "        for i,n in enumerate(graph):\n",
    "            if len(n) < min_degree:\n",
    "                min_degree = len(n)\n",
    "                min_degree_index = [i]\n",
    "            elif len(n) == min_degree:\n",
    "                min_degree_index.append(i)\n",
    "\n",
    "        finish_mode = 2**len(graph)-1\n",
    "\n",
    "        queue = collections.deque()\n",
    "        step = 0\n",
    "        visited = set()\n",
    "        for start_node in min_degree_index:\n",
    "            temp_visited = 1 << start_node\n",
    "            queue.append((start_node, temp_visited))  # 当前所在节点 和 已经参观过的节点\n",
    "            # visited.add((start_node, temp_visited))\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            step += 1\n",
    "            for _ in range(len(queue)):\n",
    "                (temp_node, temp_visited) = queue.popleft()\n",
    "                if temp_visited == finish_mode:\n",
    "                    return step - 1\n",
    "                if ((temp_node, temp_visited) in visited):\n",
    "                    continue\n",
    "                visited.add((temp_node, temp_visited))\n",
    "                for child in graph[temp_node]:\n",
    "                    new_visited = temp_visited\n",
    "                    new_visited |= (1 << child)\n",
    "                    if (child, new_visited) in visited:\n",
    "                        continue\n",
    "                    queue.append((child, new_visited))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        vis = {}\n",
    "        def f(x, s, step):\n",
    "            nonlocal ans\n",
    "            if step >= ans:\n",
    "                return\n",
    "            if (x, s) in vis and vis[(x, s)] <= step:\n",
    "                return\n",
    "            vis[(x, s)] = step\n",
    "            # print(x, s)\n",
    "            s = set([int(t) for t in s.split(\"-\")])\n",
    "            if len(s) == len(graph):\n",
    "                ans = min(ans, step)\n",
    "                return\n",
    "\n",
    "            for y in graph[x]:\n",
    "                f(y, \"-\".join(sorted([str(t) for t in s | {y}])), step + 1)\n",
    "                \n",
    "\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(len(graph)):\n",
    "            f(i, str(i), 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        \n",
    "        N = len(graph)\n",
    "        target = (1<<N)-1\n",
    "        history = {}\n",
    "        \n",
    "        graph.append(list(range(N)))\n",
    "        q = [(0,0,N)]  # distance, visited, cur_node\n",
    "        \n",
    "        while q[0][1] != target:\n",
    "            d,v,n = heapq.heappop(q)\n",
    "            if (v,n) in history: continue\n",
    "            history[(v,n)] = d\n",
    "            for nei in graph[n]:\n",
    "                nd,nv,nn = 1+d,v|(1<<nei),nei\n",
    "                if (nv,nn) in history and history[(nv,nn)]<=nd: continue\n",
    "                heapq.heappush(q,(nd,nv,nn))\n",
    "\n",
    "        return q[0][0]-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        N = len(graph)\n",
    "        q = []\n",
    "        for i in range(N):\n",
    "            q.append([1 << i, i, 0])\n",
    "        vis = set()\n",
    "        while q:\n",
    "            cover, node, dist = q.pop(0)\n",
    "            if (cover, node) in vis:\n",
    "                continue\n",
    "            vis.add((cover, node))\n",
    "            if cover == 2 ** N - 1:\n",
    "                return dist\n",
    "            for child in graph[node]:\n",
    "                q.append((cover | 1 << child, child, dist + 1))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        end = (1 << n) - 1\n",
    "        visited = {(end, i) for i in range(n)}\n",
    "        queue = [(end, i, 0) for i in range(n)]\n",
    "        idx = 0\n",
    "        while True:\n",
    "            status, start, cnt = queue[idx]\n",
    "            for ne in graph[start]:\n",
    "                if (status, ne) not in visited:\n",
    "                    queue.append((status, ne, cnt + 1))\n",
    "                    visited.add((status, ne))\n",
    "                if status & (1 << start) and (status - (1 << start), ne) not in visited:\n",
    "                    if status - (1 << start) == 1 << ne:\n",
    "                        return cnt + 1\n",
    "                    queue.append((status - (1 << start), ne, cnt + 1))\n",
    "                    visited.add((status - (1 << start), ne))\n",
    "            idx += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        def bt(node,end):\n",
    "            if dp[node][end]!=100: return dp[node][end]\n",
    "            t_node=node-base[end]\n",
    "            mask[end]=0\n",
    "            for i in range(n):\n",
    "                if mask[i]!=0:\n",
    "                    dp[node][end]=min(dp[node][end],bt(t_node,i)+floyd[i][end])\n",
    "            mask[end]=1\n",
    "            return dp[node][end]\n",
    "\n",
    "        n,m=len(graph),2**(len(graph))\n",
    "        floyd=[[100 for j in range(n)]for i in range(m)]\n",
    "        for i in range(n):\n",
    "            floyd[i][i]=0\n",
    "            for j in graph[i]:\n",
    "                floyd[i][j]=1\n",
    "                floyd[j][i]=1\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j])  \n",
    "\n",
    "        dp=[[100 for j in range(n)]for i in range(m)]\n",
    "        base=[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]\n",
    "        for i in range(n): dp[base[i]][i]=1\n",
    "        for i in range(n): \n",
    "            mask=[1]*n\n",
    "            temp=bt(m-1,i)\n",
    "        #print(dp)\n",
    "        return min(dp[-1])-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        min_step = float('inf')\n",
    "        queue = []\n",
    "        limit = set()\n",
    "        for i in range(len(graph)):\n",
    "            queue.append((i, 0, {i})) #step\n",
    "            limit.add((i, str(i)))\n",
    "        while queue:\n",
    "            status, step, visited = queue.pop(0)\n",
    "            for next_status in graph[status]:\n",
    "                if step < min_step:\n",
    "                    visited_temp = copy.deepcopy(visited)\n",
    "                    visited_temp.add(next_status)\n",
    "                    if len(visited_temp) == len(graph):\n",
    "                        min_step = step + 1\n",
    "                    else:\n",
    "                        l = list(visited_temp)\n",
    "                        l.sort()\n",
    "                        s = ''.join(list(map(str,l)))\n",
    "                        if (next_status, s) not in limit:\n",
    "                            limit.add((next_status, s))\n",
    "                            queue.append((next_status, step + 1, visited_temp))\n",
    "        return min_step if not math.isinf(min_step) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        dq = deque()\n",
    "        dct = {}\n",
    "        n = len(graph)\n",
    "        for i in range(n):\n",
    "            for j in range(1 << n):\n",
    "                dct[(i, j)] = 114514\n",
    "            dq.append((i, 1 << i))\n",
    "            dct[(i, 1 << i)] = 0\n",
    "        \n",
    "        while dq:\n",
    "            cur, mask = dq[0]\n",
    "            dq.popleft()\n",
    "            for nxt in graph[cur]:\n",
    "                if dct[(nxt, mask | (1 << nxt))] > dct[(cur, mask)] + 1:\n",
    "                    dct[(nxt, mask | (1 << nxt))] = dct[(cur, mask)] + 1\n",
    "                    dq.append((nxt, mask | (1 << nxt)))\n",
    "                \n",
    "\n",
    "        ans = 114514\n",
    "\n",
    "        for i in range(n):\n",
    "            ans = min(ans, dct[(i, (1 << n)-1)])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        #多源bfs  mask二进制表示 自己 到过哪些节点\n",
    "        visited = set() # (node ,mask)\n",
    "        \n",
    "        queue = deque()\n",
    "        lenth = len(graph)\n",
    "        target = 2**lenth -1\n",
    "        for val in range(lenth):\n",
    "            queue.append((val, 1<<val))\n",
    "            # visited.add((val, 1<<val) )\n",
    "        cnt = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                ele, mask = queue.popleft()\n",
    "                if (ele, mask) in visited:\n",
    "                    continue\n",
    "                visited.add((ele, mask))\n",
    "                if mask == target:\n",
    "                    return cnt\n",
    "                for val in graph[ele]:\n",
    "                    next_mask = mask | 1 << val\n",
    "                    queue.append((val, next_mask))\n",
    "            cnt += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        ans = inf\n",
    "        res = deque([])\n",
    "        for i in range(n):\n",
    "            res.append([i,1<<i,0])\n",
    "        has = set()\n",
    "        while res:\n",
    "            p,x,lu = res.popleft()\n",
    "            if x == (1<<n)-1:\n",
    "                return lu\n",
    "            if (p,x) in has:continue\n",
    "            has.add((p,x))\n",
    "            for i in graph[p]:\n",
    "                if (i,x|(1<<i)) in has:continue\n",
    "                res.append([i,x|(1<<i),lu+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        \n",
    "        N=len(graph)\n",
    "        \n",
    "        q=collections.deque((i,1<<i,0) for i in range(N))\n",
    "        visited=set()\n",
    "        while q:\n",
    "            index,mask,dis=q.popleft()\n",
    "            if (index,mask) in visited:\n",
    "                continue\n",
    "            visited.add((index,mask))\n",
    "            if mask==(1<<N)-1:\n",
    "                \n",
    "                return dis\n",
    "            for nxt in graph[index]:\n",
    "                mask_new=mask | (1<<nxt)\n",
    "                q.append((nxt,mask_new,dis+1))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        q = deque((i, 1<<i) for i in range(n))\n",
    "        vis = set()\n",
    "        step = 0\n",
    "        end = 2**n - 1\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if cur[1] == end:\n",
    "                    return step\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    for next_node in graph[cur[0]]:\n",
    "                        q.append((next_node, cur[1] | (1<<next_node)))\n",
    "            step += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        l = len(graph)\n",
    "        g = {}\n",
    "        n = 0\n",
    "        for i in range(l):\n",
    "            for j in graph[i]:\n",
    "                if j > n:\n",
    "                    n = j\n",
    "                if i not in g:\n",
    "                    g[i] = [j]\n",
    "                else:\n",
    "                    g[i].append(j)\n",
    "        n += 1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        rc = {}\n",
    "        def work(cur, dis, vis):\n",
    "            vistemp = sorted(vis)\n",
    "            t = tuple(vistemp)\n",
    "            if (t, cur) in rc and rc[(t, cur)] <= dis:\n",
    "                return\n",
    "            else:\n",
    "                rc[(t, cur)] = dis\n",
    "\n",
    "            for j in g[cur]:\n",
    "                f = False\n",
    "                if j not in vis:\n",
    "                    f = True\n",
    "                    vis.append(j)\n",
    "                work(j, dis+1, vis)\n",
    "                if f:\n",
    "                    vis.pop(-1)\n",
    "        \n",
    "        for i in range(n):\n",
    "            work(i, 0, [i])\n",
    "        # print(rc)\n",
    "        ans = 1e9\n",
    "        for k, v in rc.items():\n",
    "            if len(k[0]) == n:\n",
    "                ans = min(ans, v)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        min_step = float('inf')\n",
    "        queue = []\n",
    "        limit = set()\n",
    "        for i in range(len(graph)):\n",
    "            queue.append((i, 0, {i})) #step\n",
    "            limit.add((i, (i,)))\n",
    "        while queue:\n",
    "            status, step, visited = queue.pop(0)\n",
    "            for next_status in graph[status]:\n",
    "                if step < min_step:\n",
    "                    visited_temp = copy.deepcopy(visited)\n",
    "                    visited_temp.add(next_status)\n",
    "                    if len(visited_temp) == len(graph):\n",
    "                        min_step = step + 1\n",
    "                    else:\n",
    "                        if (next_status, tuple(visited_temp)) not in limit:\n",
    "                            limit.add((next_status, tuple(visited_temp)))\n",
    "                            queue.append((next_status, step + 1, visited_temp))\n",
    "        return min_step if not math.isinf(min_step) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        ans = float(\"inf\")\n",
    "        found = False\n",
    "        states = set()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(vis, last, step):\n",
    "            nonlocal ans, found\n",
    "            if found:\n",
    "                return\n",
    "            if step >= ans:\n",
    "                return\n",
    "            if vis == (1 << n) - 1:\n",
    "                ans = step\n",
    "                #print(n, ans)\n",
    "                if ans == n - 1:\n",
    "                    found = True\n",
    "                return\n",
    "\n",
    "            remain = []\n",
    "            for v in graph[last]:\n",
    "                if (vis >> v) & 1:\n",
    "                    remain.append(v)\n",
    "                    continue\n",
    "                vis2 = vis | (1 << v)\n",
    "                if (vis2, v) not in states:\n",
    "                    states.add((vis2, v))\n",
    "                    dfs(vis2, v, step + 1)\n",
    "                    states.discard((vis2, v))\n",
    "\n",
    "            for v in remain:\n",
    "                vis2 = vis | (1 << v)\n",
    "                if (vis2, v) not in states:\n",
    "                    states.add((vis2, v))\n",
    "                    dfs(vis2, v, step + 1)\n",
    "                    states.discard((vis2, v))\n",
    "\n",
    "        for last in range(n):\n",
    "            vis = 1 << last\n",
    "            states.add((vis, last))\n",
    "            dfs(vis, last, 0)\n",
    "            states.discard((vis, last))\n",
    "            if found:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "\n",
    "        queue = collections.deque()\n",
    "        hash_set = set()\n",
    "        for i in range(len(graph)):\n",
    "            queue.append([i,2 ** i,0])\n",
    "            hash_set.add(\"%d_%d\" % (i, 2 ** i))\n",
    "\n",
    "        def bfs(queue):\n",
    "            if len(queue) == 0:\n",
    "                return 0\n",
    "            nonlocal graph\n",
    "            nonlocal hash_set\n",
    "            res_queue = collections.deque()\n",
    "            for i in range(len(queue)):\n",
    "                tmp_node,tmp_mask,count = queue[i]\n",
    "                for next_node in graph[tmp_node]:\n",
    "                    next_mask = tmp_mask | 2 ** next_node\n",
    "                    if next_mask == 2 ** len(graph) - 1:\n",
    "                        return count + 1\n",
    "                    if \"%d_%d\" % (next_node,next_mask) in hash_set:\n",
    "                        continue\n",
    "                    else:\n",
    "                        hash_set.add(\"%d_%d\" % (next_node, next_mask))\n",
    "                        res_queue.append([next_node,next_mask,count+1])\n",
    "\n",
    "            return bfs(res_queue)\n",
    "\n",
    "        res = bfs(queue)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        ans = inf\n",
    "        res = deque([])\n",
    "        for i in range(n):\n",
    "            res.append([i,1<<i,0])\n",
    "        has = set()\n",
    "        while res:\n",
    "            p,x,lu = res.popleft()\n",
    "            if x == (1<<n)-1:\n",
    "                return lu\n",
    "            if (p,x) in has:continue\n",
    "            has.add((p,x))\n",
    "            for i in graph[p]:\n",
    "                if (i,x|(1<<i)) in has:continue\n",
    "                res.append([i,x|(1<<i),lu+1])\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
